package sort;
/**
*      图片真的特别有帮助
*      动图演示：https://blog.csdn.net/Websphere_zxf/article/details/109013001
*      插入排序基本思想：把n个待排序的元素看成一个有序表和一个无序表，开始有序表只包含一个元素，无序表中包含n-1个元素
*          排序过程中每次从无序表中取出第一个元素，把它的值依次与有序表倒着的值进行比较，将它插入到有序表的合适位置，使之成为新的有序表。
*      逆子 冒泡型插入 : 1.2s
 *     正规血统 插入： 0.75s
 *     其中优化在与：从"交换" ===>  移动
 */

import java.util.Arrays;
import java.util.Random;

public class insertSorting {
    public static void main(String[] args) {
        int [] array = {7,6,9,3,1,5,2,4};
        int [] array2 = {7,6};
        insert2(array);
        System.out.println(Arrays.toString(array));
        //costTime();
    }
    // 菜鸟教程给出的 '冒泡式' 插入 也就是交换法
    public static void insert(int[] arrays){
        int length = arrays.length;
        for (int i = 1; i <= length-1; i++) {
            for (int j = i; j>0; j--) {
                if (arrays[j]<arrays[j-1]){
                    swap(arrays,j,j-1);
                }else {
                    break;
                }
            }
        }
    }

    /**
     * insertVal 是即将要进行插入的值
     * index 是有序表中最后一个值的下标
     * @param arrays
     */
    // 第二种解决方案 , 移动法 最优解法
    public static void insert2(int[] arrays){
        int insertVal = 0;
        int index = 0;
        int length = arrays.length;
        for (int i = 1; i <= length-1; i++) {
            // 准备插入的数
            insertVal  = arrays[i];
            // 表示与有序表的最后元素的下标
             index = i-1;
            // 如果插入的数比被插入的数小
            while (index>=0 && insertVal<arrays[index]){
                arrays[index+1] = arrays[index];
                index--;
            }
            // //把插入的数放入合适位置
            arrays[index+1] = insertVal;
        }
    }
    // 抽取交换方法
    public static void swap(int[]arr,int i,int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    /**
     *  测试八万的数据
     */
    public static void costTime() {
        int[] arrays4 = new int[80000];
        Random random = new Random();
        for (int i = 0; i < arrays4.length; i++) {
            arrays4[i] = random.nextInt(80000);
        }
        int[] arrays3 = new int[80000];
        Random random2 = new Random();
        for (int i = 0; i < arrays3.length; i++) {
            arrays3[i] = random2.nextInt(80000);
        }

        long originStartTime = System.currentTimeMillis();
        insert(arrays4);   // 这个呢是冒泡版本的插入排序  算是一个逆子
        long originEndTime = System.currentTimeMillis();
        System.out.println("程序运行时间没有优化时间为：" + (originEndTime - originStartTime)*0.001 + "s"); //输出程序运行时间
        long startTime = System.currentTimeMillis();
        insert2(arrays3);   // 正规的插入，有值的后移
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间优化时间为：" + (endTime - startTime)*0.001 + "s"); //输出程序运行时间
    }
}
